///**
// * @Author: YCKOKO
// * @Date: 2023-04-07
// * @Time:23:10
// * @Description:
// */
//import java.util.*;
//
//public class Dijkstra {
//
//    // Step 1: 定义一个内部类，表示图中的每个顶点及其邻居和权重
//    private static class Node implements Comparable<Node> {
//        final int name;          // 顶点名称
//        int weight = Integer.MAX_VALUE;   // 到该顶点的距离
//        LinkedList<Edge> edges = new LinkedList<>(); // 邻接边
//
//        public Node(int name) {
//            this.name = name;
//        }
//
//        @Override
//        public int compareTo(Node other) {
//            return Integer.compare(weight, other.weight);
//        }
//    }
//
//    // Step 2: 定义另一个内部类，表示图中的每条边以及其权重
//    private static class Edge {
//        final Node dest;     // 目标顶点
//        final int weight;    // 边的权重
//
//        public Edge(Node dest, int weight) {
//            this.dest = dest;
//            this.weight = weight;
//        }
//    }
//
//    // Step 3: 主要方法，Dijkstra算法的实现
//    public static Map<Node, Integer> shortestPath(Node start) {
//        PriorityQueue<Node> queue = new PriorityQueue<>();
//        Map<Node, Integer> dist = new HashMap<>();
//
//        // Step 4: 初始化起点到自己的距离为0，其他顶点为无穷大，
//        // 并将所有顶点加入优先队列（按照它们到起点的距离排序）
//        start.weight = 0;
//        queue.offer(start);
//        dist.put(start, 0);
//
//        while (!queue.isEmpty()) {
//            Node u = queue.poll();
//
//            // Step 5: 遍历u的所有邻居，更新它们到起点的距离
//            for (Edge e : u.edges) {
//                Node v = e.dest;
//                int weight = e.weight;
//                int distanceThroughU = u.weight + weight;
//
//                if (distanceThroughU < v.weight) {
//                    queue.remove(v);
//
//                    v.weight = distanceThroughU;
//                    dist.put(v, distanceThroughU);
//                    v.compareTo(u);
//
//                    queue.offer(v);
//                }
//            }
//        }
//
//        return dist;
//    }
//
//    // Step 6: 测试代码
//    public static void main(String[] args) {
//        Node n1 = new Node(1);
//        Node n2 = new Node(2);
//        Node n3 = new Node(3);
//        Node n4 = new Node(4);
//        Node n5 = new Node(5);
//
//        n1.edges.add(new Edge(n2, 10));
//        n1.edges.add(new Edge(n3, 30));
//        n1.edges.add(new Edge(n4, 50));
//
//        n2.edges.add(new Edge(n4, 20));
//
//        n3.edges.add(new Edge(n4, 40));
//        n3.edges.add(new Edge(n5, 10));
//
//        n4.edges.add(new Edge(n5, 30));
//
//        Map<Node, Integer> dist = shortestPath(n1);
//
//        System.out.println(dist.get(n1));
//        System.out.println(dist.get(n2));
//        System.out.println(dist.get(n3));
//        System.out.println(dist.get(n4));
//        System.out.println(dist.get(n5));
//    }
//}


import java.util.*; // 引入Java自带的集合框架

public class Dijkstra {

    private static int INF = Integer.MAX_VALUE;

//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//
//        System.out.println("请输入节点数量和边数量：");
//        int n = scanner.nextInt();
//        int m = scanner.nextInt();
//
//        int[][] graph = new int[n][n]; // 定义邻接矩阵表示图
//
//        for (int i = 0; i < n; i++) {
//            Arrays.fill(graph[i], INF); // 初始化所有边的权值为正无穷
//        }
//
//        System.out.println("请输入每条边的起点、终点和边权：");
//        for (int i = 0; i < m; i++) {
//            int u = scanner.nextInt();
//            int v = scanner.nextInt();
//            int w = scanner.nextInt();
//            graph[u][v] = w; // 存储边权
//        }
//
//        System.out.println("请输入起点和终点：");
//        int start = scanner.nextInt();
//        int end = scanner.nextInt();
//
//        int[] dist = dijkstra(graph, start); // 调用dijkstra算法求解最短路径
//
//        if (dist[end] == INF) { // 无法到达
//            System.out.println("从起点无法到达终点！");
//        } else {
//            System.out.println("从起点到终点的最短距离为：" + dist[end]);
//        }
//    }

    public static int[] dijkstra(int[][] graph, int start) {
        int n = graph.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];

        Arrays.fill(dist,INF);

        for (int i = 0; i < n; i++) {
            dist[i] = graph[start][i];
        }

        visited[start] = true;

        for (int i = 0; i < n; i++) {
            int min_dist = INF;
            int middle = 0;

            for (int j = 0; j < n; j++) {
                if(!visited[i] && min_dist > dist[j]){
                     min_dist = dist[j];
                     middle = j;
                }
            }

            for (int j = 0; j < n; j++) {
                if(!visited[j]&&dist[j]>dist[middle]+graph[middle][j]){
                    dist[j]=dist[middle]+graph[middle][j];
                }
            }
            visited[middle] = true;
        }
        return dist;
    }

    public static void main(String[] args) {

    }
}

